package RKUjava.datastructures;
import java.util.Enumeration;
import java.io.Serializable;
import java.util.NoSuchElementException;
import RKUjava.util.RKUQuickSort;
import RKUjava.util.RKUArrays;
import java.util.Arrays;
import java.util.Comparator;

/** The RKUVector implements a type of vector useful in some cases
    where the features of the standard vector is cumbersome.
    The RKUVector is a full implementation in the sense that
    supports the same methods as Sun's Vector + some extra.
    The major differences from Sun's implementation are:
    <ul>
    <li> Supports quicksorting via RKUQuickSort
    <li> It also support resetting the vector and nullify the contents. 
    (I'm not sure this is done when you call removeAllElements() on the 
    standard Vector - if not the Garbage Collector can't free the memory.) 
    <li> The elements() method returns <tt>this</tt> instead of Sun's
    way (AFAIK they create an anonymous subclass of the interface Enumeration).
    If you have a huge number of Vectors (say 20000) you want to traverse 
    often, then doing it the Sun way will create and destroys 20000 
    objects every time you traverse the vectors. (Quite a load on the garbage 
    collector.)
    <li> The RKUVector also supports direct updating of the elementData from
    an array and other methods for faster use of the Vector. 
    </ul>
    @see RKUjava.util.RKUQuickSort 
    @see RKUjava.datastructures.RKULightVector
*/

public class RKUVector implements Serializable, Cloneable, Enumeration
{
  /** 
    @serial
  */
  protected int elementCount;
  /** 
    @serial
  */
  protected Object[] elementData;
  /** 
    @serial
  */
  protected int capacityIncrement;
  /** 
    @serial
  */
  private int curenumindex;

  /** Construct an empty vector with the default initial capacity 
      (10 elements).
   */
  public RKUVector()
    {
      capacityIncrement = 0;
      elementCount = 0;
      elementData = new Object[10];
    }

  /** Construct an empty vector with the specified initial capacity.
      @param initialCapacity the initial capacity of the vector.
  */
  public RKUVector(int initialCapacity)
    {
      capacityIncrement = 0;
      elementCount = 0;
      elementData = new Object[initialCapacity];
    }


  /** Construct an empty vector with the specified initial capacity.
      @param initialCapacity the initial capacity of the vector.
  */
  public RKUVector(int initialCapacity, int capacityincrement)
    {
      capacityIncrement = capacityincrement;
      elementCount = 0;
      elementData = new Object[initialCapacity];
    }

  /** Add an array to this vector. 
      @param anArray[] The array to append to the vector.
  */
  public void addArray(Object anArray[])
    {
      int i, j;
      this.ensureCapacity(elementCount+anArray.length);

      j = elementCount;
      for (i=0;i<anArray.length;i++) {
	elementData[j] = anArray[i];
	j++;
      }
      elementCount = elementCount+anArray.length;
    }

  /** Add a vector to this vector. The elements in the given 
      vector are copied to this vector.
      @param aVector The vector to append to the vector.
  */
    public void addVector(RKUVector aVector)
    {
      int i, j;
      this.ensureCapacity(elementCount+aVector.size());

      j = elementCount;
      for (i=0;i<aVector.size();i++) {
	elementData[j] = aVector.elementAt(i);
	j++;
      }
      elementCount = elementCount+aVector.size();

    };
  /** Copies the components of this vector into the specified array.
      The array must be big enough to hold all the objects in this vector. 
      @param anArray the array into which the components get copied.
  */
  public synchronized void copyInto(Object anArray[])
    {
      for (int i=0;i<elementCount;i++) {
	anArray[i] = elementData[i];
      }
    }

  /** Get the elementData array. This is a very lowlevel method, but it
      can be used to overcome some copying back and forth.<br>
      <b>Note:</b> If
      you change the array in any way it will also affect the vector!
      Remember that the returned array might be longer than the 
      actual number of elements in the array.
  */
  public Object[] getElementData()
    {
      return elementData;
    }

    /** Get the elements as an array. This is equivalent to creating an 
	array yourself an then use the copyInto method.
    */
    public synchronized Object[] getElementsAsArray()
    {
	Object[] res = new Object[elementCount];
	copyInto(res);

	return res;
    }

    /** Get the elements as an array. This is equivalent to creating an 
	array yourself an then use the copyInto method.
    */
    public synchronized Object[] toArray()
    {
	Object[] res = new Object[elementCount];
	copyInto(res);

	return res;
    }

  /** Replace the entries in this vectors elementData with the ones from
      newData[]. <b>Note:</b> The values are COPIED from newData to the
      elementData array. The number of elements after is equal to the number
      of elements in newData[].<br>If you want to replace the whole array
      use the method replaceDataArray().
      @param newData The new data to install in this RKUVector.
      @see RKUjava.datastructures.RKUVector#replaceDataArray

  */
  public synchronized void replaceDataEntries(Object newData[])
    {
      if (elementData.length<newData.length) {
	elementData = new Object[newData.length];
      };

      for (int i=0;i<newData.length;i++) {
	elementData[i] = newData[i];
      }

      elementCount = elementData.length;
    }

  /** Replace this vectors elementData with newData[]. 
      <b>Note:</b> The elementData array is replaced with newData. 
      The number of elements after is equal to the number
      of elements in newData[].<br>If you want to copy the  elements from
      newData use the method replaceDataEntries().
      @param newData The new data to install in this RKUVector.
      @see RKUjava.datastructures.RKUVector#replaceDataEntries

  */
  public synchronized void replaceDataArray(Object newData[])
    {
      elementData = newData;
      elementCount = newData.length;
    }

  /** Iterate through the vector and do something for each element. 
      This method iterates the vector and calls iterator.handleElement for
      each element in the vector.
      @param iterator Implementation of the actions to perform on each element.
  */
  public synchronized void iterate(RKUIterator iterator)
    {
      int i;

      for (i=0;i<elementCount;i++) {
	iterator.handleElement(elementData[i]);
      }
    }

  /** Trims the capacity of this vector to be the vector's current size.
      An application can use this operation to minimize the storage of a 
      vector. 
  */
  public synchronized void trimToSize()
    {
      Object[] newarray;
      newarray = new Object[elementCount];
      copyInto(newarray);
      elementData = newarray;
    }

  /** Increases the capacity of this vector, if necessary, to ensure that 
      it can hold at least the number of components specified by the 
      minimum capacity argument. 
      @param minCapacity the desired minimal capacity.
  */
  public synchronized void ensureCapacity(int minCapacity)
    {
      Object[] newarray;

      if (elementData.length<minCapacity) {
	newarray = new Object[minCapacity];
	copyInto(newarray);
	elementData = newarray;
      }
    }

  /** Sets the size of this vector. If the new size is greater than 
      the current size, new null items are added to the end of the 
      vector. If the new size is less than the current size, 
      all components at index newSize and greater are discarded. 
      @param newSize the new size of this vector. 
  */
  public synchronized void setSize(int newSize)
    {
      Object[] newarray;
      newarray = new Object[newSize];
      elementCount = newSize;
      copyInto(newarray);
      elementData = newarray;
    }

  /** Returns the current capacity of this vector. 
      @return the current capacity of this vector. 
  */
  public int capacity()
    {
      return elementData.length;
    }

  /** Returns the number of components in this vector. 
      @return the number of components in this vector. 
  */
  public int size()
    {
      return elementCount;
    }


  /** Tests if this vector has no components. 
      @return true if this vector has no components; false otherwise. 
  */
  public boolean isEmpty()
    {
      return (elementCount == 0);
    }

  /** Returns an enumeration of the components of this vector. Since the 
      RKUVector implements the Enumeration interface it resets its index and
      return a pointer to itself.
      @return an enumeration of the components of this vector. 
      @see RKUEnumeration 
  */
  public synchronized Enumeration elements()
    {
      curenumindex = 0;
      return this;
    }

  /** Tests if the specified object is a component in this vector. 
      @param elem an object. 
      @return true if the specified object is a component in this vector; 
      false otherwise.
  */
  public boolean contains(Object elem)
    {
      return (indexOf(elem)!=-1);
    }

  /** Searches for the first occurence of the given argument, testing for 
      equality using the equals method. 
      @param elem an object. 
      @return the index of the first occurrence of the argument in this vector; returns -1 if the object is not found. 
  */
  public int indexOf(Object elem)
    {
      for (int i=0;i<elementCount;i++) {
	if(elem.equals(elementData[i]))
	  return i;
      }
      return -1;
    }


  /** Searches for the first occurence of the given argument, beginning the search at index, and testing for equality using the equals method. 
      @param elem an object. 
      @param index the index to start searching from. 
      @return the index of the first occurrence of the object argument in this vector at position index or later in the vector; returns -1 if the object is not found. 
  */
  public synchronized int indexOf(Object elem, int index)
    {
      for (int i=index;i<elementCount;i++) {
	if(elem.equals(elementData[i]))
	  return i;
      }
      return -1;
    }

  /** Returns the index of the last occurrence of the specified object 
      in this vector. 
      @param elem the desired component. 
      @param return the index of the last occurrence of the specified object in this vector; returns -1 if the object is not found. 
  */
  public int lastIndexOf(Object elem)
    {
      for (int i=elementCount-1;i>=0;i--) {
	if(elem.equals(elementData[i]))
	  return i;
      }
      return -1;
    }

  /** Searches backwards for the specified object, starting from the 
      specified index, and returns an index to it. 
      @param elem the desired component. 
      @param index the index to start searching from. 
      @return the index of the last occurrence of the specified object in 
      this vector at position less than index in the vector; -1 if the 
      object is not found. 
  */
  public synchronized int lastIndexOf(Object elem, int index)
    {
      for (int i=index;i>=0;i--) {
	if(elem.equals(elementData[i]))
	  return i;
      }
      return -1;
    }
  
  /** Returns the component at the specified index. 
      @param index an index into this vector. 
      @return the component at the specified index. 
      @exception ArrayIndexOutOfBoundsException if an invalid index was given. 
  */
  public synchronized Object elementAt(int index)
    {
      if (index<0 || index>=elementCount)
	  if (elementCount==0) 
	      throw new ArrayIndexOutOfBoundsException("Cannot return object with index="+index+". The vector is empty!");
	  else
	      throw new ArrayIndexOutOfBoundsException("Cannot return object with index="+index+". It must be between 0 and "+(elementCount-1)+" (both included)");
      else
	return elementData[index];
    }

  /** Returns the first component of this vector. 
      @return the first component of this vector. 
      @exception NoSuchElementException if this vector has no components. 
  */
  public synchronized Object firstElement()
    {
      if (elementCount==0)
	throw new NoSuchElementException("The vector is empty.");
      else
	return elementData[0];
    }

  /** Returns the last component of this vector. 
      @return the last component of this vector. 
      @exception NoSuchElementException if this vector has no components. 
  */
  public synchronized Object lastElement()
    {
      if (elementCount==0)
	throw new NoSuchElementException("The vector is empty.");
      else
	return elementData[elementCount-1];
    }

  /** Sets the component at the specified index of this vector to be 
      the specified object. The previous component at that position 
      is discarded. The index must be a value greater than or equal 
      to 0 and less than the current size of the vector. 

      @param obj what the component is to be set to. 
      @param index the specified index. 
      @exception ArrayIndexOutOfBoundsException if the index was invalid. 
  */
  public synchronized void setElementAt(Object obj, int index)
    {
      if (index<0 || index>=elementCount)
	throw new ArrayIndexOutOfBoundsException("Cannot set object with index="+index+". It must be between 0 and "+(elementCount-1)+" (both included)");
      else
	elementData[index] = obj;
    }

  /** Deletes the component at the specified index. Each component in 
      this vector with an index greater or equal to the specified 
      index is shifted downward to have an index one smaller than 
      the value it had previously. <br><br>
      The index must be a value greater than or equal to 0 and less
      than the current size of the vector.

      @param index the index of the object to remove. 
      @exception ArrayIndexOutOfBoundsException if the index was invalid. 
  */
  public synchronized void removeElementAt(int index)
    {
      if (index<0 || index>=elementCount)
	throw new ArrayIndexOutOfBoundsException("Cannot remove object with index="+index+". It must be between 0 and "+(elementCount-1)+" (both included)");
      else 
	shrink(index);
    }

  /** Inserts the specified object as a component in this vector at the 
      specified index. Each component in this vector with an index 
      greater or equal to the specified index is shifted upward to 
      have an index one greater than the value it had previously. <br><br>
      The index must be a value greater than or equal to 0 and less 
      than or equal to the current size of the vector. 
      @param obj the component to insert. 
      @param index where to insert the new component. 
      @exception ArrayIndexOutOfBoundsException if the index was invalid. 
  */
  public synchronized void insertElementAt(Object obj, int index)
    {
      if (index>elementCount || index<0)
	throw new ArrayIndexOutOfBoundsException("Cannot insert object with index="+index+". It must be between 0 and "+elementCount+" (both included)");
      else {
	enlarge(index);
	elementData[index] = obj;
      }
    }

  /** Adds the specified component to the end of this vector,
      increasing its size by one. The capacity of this vector is
      increased if its size becomes greater than its capacity. 

      @param obj the component to be added. 
  */
  public synchronized void addElement(Object obj)
    {
      if (elementCount==elementData.length)
	incrementsize();
      
      elementData[elementCount] = obj;
      elementCount++;
    }

  /** Removes the first occurrence of the argument from this vector. If the
      object is found in this vector, each component in the vector with an
      index greater or equal to the object's index is shifted downward to
      have an index one smaller than the value it had previously. 

      @param obj the component to be removed. 
      @return true if the argument was a component of this vector; false
      otherwise. 
  */
  public synchronized boolean removeElement(Object obj)
    {
      int index = indexOf(obj);

      if (index!=-1)
	shrink(index);

      return (index!=-1);
    }
  
  /** Removes all components from this vector and sets its size to zero. 
      This method also sets all indexes to null so the garbage collector
      can free the memory. 
   */
  public synchronized void removeAllElements()
    {
      for(int i=0;i<elementCount;i++) {
	elementData[i]=null;
      }
      elementCount = 0;
    }

  /** Removes all components from this vector and sets its size to zero. 
      This method only sets the elementCount to zero. You can use 
      removeElementsAfter to clear the nonindexable fields.<br>
      The following sequence can be faster than an invokation of 
      removeAllElements()
      <ol>
      <li> ...
      <li> myvector.removeElementsFast();
      <li> ** Add some elements to myvector **
      <li> myvector.removeElementsAfter(myvector.size());
      <li> ...
      </ol>
   */
  public synchronized void removeAllElementsFast()
    {
      elementCount = 0;
    }

  /** Remove all elements starting at a given index. This method also 
      sets all entries after elementCount to null. If you 
      invoke with index=0 all elements are removed.
      @param index The index to start at.
      @see RKUjava.datastructures.RKUVector#removeAllElementsFast
  */
  public synchronized void removeElementsAfter(int index)
    {
      for(int i=index;i<elementData.length;i++) {
	elementData[i]=null;
      }
      elementCount = index;
    }

  /** Returns a clone of this vector. 
   */
  public synchronized Object clone()
    {
      RKUVector res;
      
      res = new RKUVector(elementData.length);
      copyInto(res.elementData);
      res.elementCount = this.elementCount;

      return res;
    }

  /** Returns a string representation of this vector. 
      @return a string representation of this vector. 
  */
  public synchronized String toString()
    {
      return super.toString();
    }

  /** Quicksort the vector. Remember that all objects must implement the
      RKUOrdering interface found in the package RKUjava.util.
      @see RKUjava.util.RKUOrdering 
      @see RKUjava.util.RKUQuickSort
  */
  public synchronized void quickSort()
    {
      RKUQuickSort.quickSort(elementData, 0, elementCount);
    }

  /** Quicksort the vector using java 1.2's Arrays.sort. 
      @param c A comparator that implements the ordering.
      @see RKUjava.util.RKUComparator
  */
  public synchronized void quickSort(Comparator c)
    {
      Arrays.sort(elementData, 0, elementCount, c);
    }

  /** Get the maximal element in the array with respect to the ordering 
      implemented by <tt>c</tt>.
  */
  public Object getMax(Comparator c)
    {
      return RKUArrays.getMax(elementData,0,elementCount,c);
    }

  /** Get the minimal element in the array with respect to the ordering 
      implemented by <tt>c</tt>.
  */
  public Object getMin(Comparator c)
    {
      return RKUArrays.getMin(elementData,0,elementCount,c);
    }

  /** Get the index of the maximal element in the array with respect to the ordering 
      implemented by <tt>c</tt>.
  */
  public int getIndexOfMax(Comparator c)
    {
      return RKUArrays.getIndexOfMax(elementData,0,elementCount,c);
    }

  /** Get the index of the minimal element in the array with respect to the ordering 
      implemented by <tt>c</tt>.
  */
  public int getIndexOfMin(Comparator c)
    {
      return RKUArrays.getIndexOfMin(elementData,0,elementCount,c);
    }

  /** Implementation of the Enumeration interface. */
  public boolean hasMoreElements()
    {
      return (curenumindex<elementCount);
    }

  /** Implementation of the Enumeration interface. */
  public Object nextElement()
    {
      curenumindex++;
      return elementAt(curenumindex-1);
    }

  // *************** Helper methods **************************

  
  /** Shrink the vector by one by copying elementData[i+1] to 
      elementData[i] for all elements in the range from index to elementCount.
      Calling shrink(0) will remove the first element and move all other 1
      field down.
  */
  protected void shrink(int index)
    {
      if (index+1<=elementCount) {
	for (int i=index+1;i<elementCount;i++) {
	  elementData[i-1] = elementData[i];
	}
	elementCount--;
	elementData[elementCount] = null;
      }
    }

  /** Enlarge the vector by one by copying elementData[i] to 
      elementData[i+1] for all elements in the range from 
      index to elementCount.
      Calling enlarge(0) will move the first element to the second position,
      second to third, third to forth etc.
      The moving is of course done reversed so the element are not overwritten.
      If the array is full its size is doubled.
  */
  protected void enlarge(int index)
    {
      if (elementCount==elementData.length)
	incrementsize();

      for (int i=elementCount;i>index;i--) {
	elementData[i] = elementData[i-1];
      }
      elementCount++;
    }

  /** Increment the size of the vector. */
  protected void incrementsize()
    {
      Object[] newarray;

      if (capacityIncrement==0)
	newarray = new Object[2*elementData.length];
      else
	newarray = new Object[elementData.length+capacityIncrement];

      copyInto(newarray);
      elementData = newarray;
    }

}
